package 二叉搜索树;


import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;

public class BinarySearchTree<E> extends BinaryTree {

    private Comparator<E> comparator;

    public BinarySearchTree() { // compareable这种方法，比较器是空的
        this(null);
    }


    public BinarySearchTree(Comparator<E> comparator) {
        this.comparator = comparator;
    }


    // 层序遍历， 翻转二叉树
    public void invert() {
        if (this.root == null) {
            return;
        }
        Queue<Node<E>> queue = new LinkedList<Node<E>>();
        queue.offer(this.root);
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            // 操作
            Node<E> temp;
            temp = node.left;
            node.left = node.right;
            node.right = temp;

//            System.out.println(node.element);


            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }

    // 前驱节点
    public Node<E> predocessor(Node<E> node) {
        if (node == null) return null;
        Node<E> p = node.left;
        // 说明前驱节点在左子树当中， left.right.right.right
        if (p != null) {
            // 在左子树里面找前驱
            while (p.right != null) {
                p = p.right;
            }
            return p;
        }
        // 说明前驱节点在祖父节点当中， parent.parent.parent.parent， 直到是自己不是parent的左节点
        while (p.parent != null && p == p.parent.left) {
            p = p.parent;
        }
        if (p.parent == null) return null; // p.parent == null
        return p; //  p = p.parent.right
    }

    // 后继节点
    public Node<E> successor(Node<E> node) {
        if (node == null) return null;

        Node<E> s = node.right;
        // 说明前驱节点在左子树当中， right.left.left.left
        if (s != null) {
            // 在左子树里面找前驱
            while (s.left != null) {
                s = s.left;
            }
            return s;
        }
        // 说明前驱节点在祖父节点当中， parent.parent.parent.parent， 直到是自己不是parent的左节点
        while (s.parent != null && s == s.parent.right) {
            s = s.parent;
        }
        if (s.parent == null) return null; // p.parent == null
        return s; //  s = s.parent.left
    }



    public void add(E element) {
        if (this.root == null) {
            this.root = new Node<E>(element, null);
            this.size++;
            return;
        }
        // 1.找到父节点和方向
        Node<E> parent = root;
        int cmp = 0;

        Node<E> node = root;
        while (node != null) {
            cmp = this.compare(element, node.element);
            parent = node;
            if (cmp > 0) {
                node = node.right;
            } else if (cmp < 0) {
                node = node.left;
            } else { // 如果相等什么都不做
                return;
            }
        }

        // 2.将新节点放上去
        Node<E> newNode = new Node<E>(element, parent);
        if (cmp > 0) {
            parent.right = newNode;
        } else {
            parent.left = newNode;
        }
        this.size++;
    }

    // 删除某个元素
    public void remove(E element) {
        this.remove(this.getNode(element));
    }

    //  根据元素获得节点
    private Node<E> getNode(E element) {
        Node<E> node = root;
        // 搜索
        while (node != null) {
            int cmp = this.compare(element, node.element);
            if (cmp == 0) return node; // 找到
            if (cmp > 0) {
                node = node.right;
            } else {
                node = node.left;
            }
        }
        // 没找到
        return null;
    }

    // 删除某个节点
    private void remove(Node<E> node) {
        if (node == null) return;
        size--;

        // 度为2
        if (node.hasTwoChildren()) {
            Node<E> sNode = this.successor(node); // 拿后继节点， 前驱节点一定是度为0的或者度为1的
            // 后继节点覆盖
            node.element = sNode.element;
            // 删除后继节点
            node = sNode; // 现在让node也指向了度为1和度为0的节点， 后面统一删除node
            // 用
        }

        // 删除node节点（node的度必然为1或者0）
        Node<E> replacement = node.left != null ? node.left : node.right; // replacement就是被删除节点的子节点
        if (replacement != null) {// 度为1
            replacement.parent = node.parent;
            if (node.parent == null) { // node == root
                root = replacement;
                replacement.parent = null; //
            } else if (node == node.parent.left) {
                node.parent.left = replacement;
            } else {
                node.parent.right = replacement;
            }
        } else {// 度为0
            if (node.parent == null) { // node == root, 根节点是叶子节点
                this.root = null;
            } else {
                if (node == node.parent.left) {
                    node.parent.left = null;
                } else {
                    node.parent.right = null;
                }
            }
        }
    }


    public boolean contains(E element) {
        return this.getNode(element) == null;
    }


    // 如果 <0 e1 < e2, 如果 > 2 e1 > e2, 如果 =0 e1 = e2
    private int compare(E e1, E e2) {
        if (comparator != null) {
            return this.comparator.compare(e1, e2);
        }
        return ((Comparable<E>) e1).compareTo(e2); // 强转失败也就是说他自身不是可比较的，也就是说即没有传比较器自身也不可比较
    }

    //    树的节点元素不能为空
    private void elementNotNullCheck(E element) {
        if (element == null) {
            throw new IllegalArgumentException("element不能为空");
        }
    }


}
